Data storage media which contain a chip are used in a large number of different applications, for example in order to carry out financial transactions, for payment for goods or services, or as an identification means for controlling access checks. In all these applications, secret data which must be protected against access by unauthorized third parties is generally processed within the chip of the data storage medium. This protection is ensured inter alia by the fact that the internal structures of the chip have very small dimensions so that access to these structures with the aim of extracting data which is being processed in these structures is very difficult. In order to make access even harder, the chip can be embedded in a very securely adhering compound whose forced removal results in the semiconductor wafer being destroyed, or at least in the secret data stored in it being erased. It is likewise also possible to provide the semiconductor wafer with a protective layer during its production process, which cannot be removed without destroying the semiconductor wafer.
With appropriate technical equipment, which admittedly is extremely expensive but is nevertheless in principle available, it would be possible for an attacker to expose the internal structure of the chip, and to investigate it. The internal structure of the chip could be exposed, for example, by means of special etching methods or by means of a suitable grinding process. The structures of the chip exposed in this way, such as interconnects, could be made contact with using microprobes or could be investigated using other methods in order to determine the signal waveforms in these structures. It would then be possible to attempt to use the detected signals to determine secret data from the data storage medium, such as secret keys, in order to use these for manipulation purposes. It would likewise be possible to attempt to deliberately influence the signal waveforms in the exposed structures via the microprobes.
Recently, furthermore, methods have become known which allow the secret data, in particular the secret key, to be deduced by measuring the current consumption or the timing for the encryption process (Paul C. Kocher, “Timing Attacks on implementation of Diffie-Hellman, RSA, DSS, and other Systems”, Springer Verlag 1998; WO 99/35782).
One simple attack of this type is the “Simple Power Analysis” (SPA). In this analysis method, by way of example, a known message M is subjected to encryption using a secret key d, that is to say the encrypted text Y=Md mod n is formed. During the modular exponentiation process, a squaring operation is carried out with the intermediate result and a multiplication operation is carried out with M if there is a “1” in the exponent d, while only a squaring operation with the intermediate result is carried out if there is a “0” in d. If M is known, the times at which the message M is used can be identified by observing the current response and/or the timing during the operations. Since this message is always used if a “1” is present in d, the key can be deduced without any problems.
This attack can be countered by making changes in the message M or in the key d. Analysis methods are, however, known from Paul C. Kocher, “Timing attacks on implementation of Diffie-Hellman, RSA, DSS, and other Systems”, Springer Verlag 1998 and from the international patent application WO 99/35782, in which the key can be deduced even if the message or the key is modified, that is to say scrambled, by recording a large number of measurement curves in which the current response of the integrated circuit is measured (“Differential Power Analysis” (DPA) or Higher Order DPA).
In order to make it impossible to identify the key easily by identifying, during the calculation process, the use of the message to be encrypted, it has already been proposed for a factor r*n to be added for the encryption of the message. The encryption text Y=Md mod n is thus changed to (M+r*n)d mod n. This means that it is impossible to get back to the known message M in an analysis process. However, even with this change to the message text M, repetition of specific patterns can be identified by observing the current curve. There is a high probability of these correlated patterns containing (M+r*n), so that in this case as well, it is possible to deduce the multiplication and hence a 1 in the secret key.
A further problem occurs if it is possible to identify during the current analysis process whether a multiplication process is carried out using the same factors (which corresponds to a squaring operation with the intermediate result) or different factors (which corresponds to a multiplication operation of the intermediate result by the message), since it is also in this way possible to identify multiplications by (M+r*n).